//
//  Problem3.swift
//  LeetCode
//
//  Created by zhulongiMac02 on 2018/8/29.
//  Copyright © 2018年 zhulongiMac02. All rights reserved.
//

import UIKit

/**
 3. 无重复字符的最长子串
 给定一个字符串，找出不含有重复字符的最长子串的长度。
 
 示例 1:
 
 输入: "abcabcbb"
 输出: 3
 解释: 无重复字符的最长子串是 "abc"，其长度为 3。
 示例 2:
 
 输入: "bbbbb"
 输出: 1
 解释: 无重复字符的最长子串是 "b"，其长度为 1。
 示例 3:
 
 输入: "pwwkew"
 输出: 3
 解释: 无重复字符的最长子串是 "wke"，其长度为 3。
 请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。
 
 */
class Problem3 {

    func solution() {
        let array = ["abcabcbb", "bbbbb", "aab", "dvdf", "pwwkew", "nfpdmpi", "wslznzfxojzd"]
        for str in array {
            let count = self.lengthOfLongestSubstrings(str)
            print(str, count)
        }
    }
    
    // arr[Character] 可以优化成 dic[Character: Int]，时间复杂度降低
    func lengthOfLongestSubstrings(_ s: String) -> Int {
        if s.count < 2 {
            return s.count
        }
        
        var count = 1
        var arr = [Character]()
        
        var i = s.startIndex
        arr.append(s[i])
        
        i = s.index(after: i)
        while i != s.endIndex {
            let c = s[i]
            
            let index = self.getCharacter(array: arr, c: c)
            if index != -1 {
                if count < arr.count {
                    count = arr.count
                }
                arr.removeSubrange((0..<index+1))       //
            }
            
            arr.append(c)
            i = s.index(after: i)
        }
        
        return count < arr.count ? arr.count : count
    }
    
    func getCharacter(array:[Character], c:Character) -> Int {
        for (index, value) in array.enumerated() {
            if value == c {
                return index
            }
        }
        return -1
    }
}
